package leetcode.tree_problem;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class 从中序与后序遍历序列构造二叉树 {
    int index = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int[] reversePostOrder = new int[postorder.length];
        for (int i = 0; i < postorder.length; i++) {
            reversePostOrder[i] = postorder[postorder.length - i - 1];
        }
        return buildHelp(inorder , reversePostOrder , 0 , postorder.length - 1);
    }
    public TreeNode buildHelp(int[] inOrder, int[] postOrder , int left , int right){
        if (left > right){
            return null;
        }
        if (index == postOrder.length){
            return null;
        }
        TreeNode root = new TreeNode(postOrder[index]);
        index ++ ;

        int curIndex = findIndex(root , inOrder);
        root.right = buildHelp(inOrder , postOrder, curIndex + 1 , right);//边界是右不要写inOrder.length - 1会省略传值过程
        root.left = buildHelp(inOrder , postOrder , left, curIndex - 1);//注意不要写0到curIndex左右值边界条件会变；
        return root;
    }
    public int findIndex(TreeNode root , int[] inOrder){
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == root.val){
                return i;
            }
        }
        return -1;

    }

}
